package dataStruct;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 剑指 Offer 06. 从尾到头打印链表
 * <p>
 * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
 * <p>
 * 示例 1：
 * <p>
 * 输入：head = [1,3,2]
 * <p>
 * 输出：[2,3,1]
 */
public class reversePrint {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 使用栈辅助
     * <p>
     * 执行用时：1 ms, 在所有 Java 提交中击败了 69.31% 的用户
     * <p>
     * 内存消耗： 39.2 MB, 在所有 Java 提交中击败了 22.62% 的用户
     * <p>
     * 通过测试用例： 24 / 24
     */
    public static int[] reversePrint_1(ListNode head) {
        Deque<Integer> stack = new ArrayDeque<>();
        ListNode p = head;
        while (p != null) {
            stack.push(p.val);
            p = p.next;
        }
        int[] arr = new int[stack.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = stack.pop();
        }
        return arr;
    }

    /**
     * 递归方法实现
     */


    public static void main(String[] args) {
        ListNode head = new ListNode(5);
        ListNode h2 = new ListNode(4);
        ListNode h3 = new ListNode(3);
        head.next = h2;
        h2.next = h3;
        h3.next = null;
        for (int i : reversePrint_1(head)) {
            System.out.println(i);
        }
    }

}
